// Common/Wildcard.cpp

#include "StdAfx.h"

#include "Wildcard.h"


bool g_CaseSensitive =
  #ifdef _WIN32
    false;
  #else
    true;
  #endif


namespace Common
{

namespace FileSystem
{


static const wchar_t kAnyCharsChar = _T('*');
static const wchar_t kAnyCharChar = _T('?');

#ifdef _WIN32
static const wchar_t kDirDelimiter1 = _T('\\');
#endif
static const wchar_t kDirDelimiter2 = _T('/');

static const CString kWildCardCharSet = _T("?*");

static const CString kIllegalWildCardFileNameChars=
  _T("\x1\x2\x3\x4\x5\x6\x7\x8\x9\xA\xB\xC\xD\xE\xF")
  _T("\x10\x11\x12\x13\x14\x15\x16\x17\x18\x19\x1A\x1B\x1C\x1D\x1E\x1F")
  _T("\"/:<>\\|");


static inline bool IsCharDirLimiter(wchar_t c)
{
  return (
    #ifdef _WIN32
    c == kDirDelimiter1 ||
    #endif
    c == kDirDelimiter2);
}

int CompareFileNames(const CString &s1, const CString &s2)
{
  if (g_CaseSensitive)
    return s1.Compare(s2);
  return s1.CompareNoCase(s2);
}

// -----------------------------------------
// this function compares name with mask
// ? - any char
// * - any char or empty

static bool EnhancedMaskTest(const wchar_t *mask, const wchar_t *name)
{
  for (;;)
  {
    wchar_t m = *mask;
    wchar_t c = *name;
    if (m == 0)
      return (c == 0);
    if (m == kAnyCharsChar)
    {
      if (EnhancedMaskTest(mask + 1, name))
        return true;
      if (c == 0)
        return false;
    }
    else
    {
      if (m == kAnyCharChar)
      {
        if (c == 0)
          return false;
      }
      else if (m != c)
        //if (g_CaseSensitive || MyCharUpper(m) != MyCharUpper(c))
		if (g_CaseSensitive || CharUpperW((LPWSTR)m) != CharUpperW((LPWSTR)c))
          return false;
      mask++;
    }
    name++;
  }
}

// --------------------------------------------------
// Splits path to strings

void SplitPathToParts(const CString &path, CStringVector &pathParts)
{
  pathParts.clear();
  CString name;
  int len = path.GetLength();
  if (len == 0)
    return;
  for (int i = 0; i < len; i++)
  {
    wchar_t c = path[i];
    if (IsCharDirLimiter(c))
    {
		pathParts.push_back(name);
      name.Empty();
    }
    else
      name += c;
  }
  pathParts.push_back(name);
}

void SplitPathToParts(const CString &path, CString &dirPrefix, CString &name)
{
  int i;
  for (i = path.GetLength() - 1; i >= 0; i--)
    if (IsCharDirLimiter(path[i]))
      break;
  dirPrefix = path.Left(i + 1);
  name = path.Mid(i + 1);
}

CString ExtractDirPrefixFromPath(const CString &path)
{
  int i;
  for (i = path.GetLength() - 1; i >= 0; i--)
    if (IsCharDirLimiter(path[i]))
      break;
  return path.Left(i + 1);
}

CString ExtractFileNameFromPath(const CString &path)
{
  int i;
  for (i = path.GetLength() - 1; i >= 0; i--)
    if (IsCharDirLimiter(path[i]))
      break;
  return path.Mid(i + 1);
}


bool CompareWildCardWithName(const CString &mask, const CString &name)
{
  return EnhancedMaskTest(mask, name);
}

bool DoesNameContainWildCard(const CString &path)
{
  return (path.FindOneOf(kWildCardCharSet) >= 0);
}


// ----------------------------------------------------------'
// Wildcard

namespace Wildcard {


/*
M = MaskParts.Size();
N = TestNameParts.Size();

                           File                          Dir
ForFile     req   M<=N  [N-M, N)                          -
         nonreq   M=N   [0, M)                            -
 
ForDir      req   M<N   [0, M) ... [N-M-1, N-1)  same as ForBoth-File
         nonreq         [0, M)                   same as ForBoth-File

ForBoth     req   m<=N  [0, M) ... [N-M, N)      same as ForBoth-File
         nonreq         [0, M)                   same as ForBoth-File

*/

bool CItem::CheckPath(const CStringVector &pathParts, bool isFile) const
{
  if (!isFile && !ForDir)
    return false;
  int delta = (int)pathParts.size() - (int)PathParts.size();
  if (delta < 0)
    return false;
  int start = 0;
  int finish = 0;
  if (isFile)
  {
    if (!ForDir && !Recursive && delta !=0)
      return false;
    if (!ForFile && delta == 0)
      return false;
    if (!ForDir && Recursive)
      start = delta;
  }
  if (Recursive)
  {
    finish = delta;
    if (isFile && !ForFile)
      finish = delta - 1;
  }
  for (int d = start; d <= finish; d++)
  {
    size_t i;
    for (i = 0; i < PathParts.size(); i++)
      if (!CompareWildCardWithName(PathParts[i], pathParts[i + d]))
        break;
    if (i == PathParts.size())
      return true;
  }
  return false;
}

int CCensorNode::FindSubNode(const CString &name) const
{
  for (size_t i = 0; i < SubNodes.size(); i++)
    if (CompareFileNames(SubNodes[i]->Name, name) == 0)
      return i;
  return -1;
}

void CCensorNode::AddItemSimple(bool include, std::shared_ptr<CItem> &item)
{
  if (include)
	  IncludeItems.push_back(item);
  else
	  ExcludeItems.push_back(item);
}

void CCensorNode::AddItem(bool include, std::shared_ptr<CItem> &item)
{
  if (item->PathParts.size() <= 1)
  {
    AddItemSimple(include, item);
    return;
  }
  const CString &front = item->PathParts.front();
  if (DoesNameContainWildCard(front))
  {
    AddItemSimple(include, item);
    return;
  }
  int index = FindSubNode(front);
  if (index < 0)
  {
	  std::shared_ptr<CCensorNode> node = std::make_shared<CCensorNode>(front, this);
	  SubNodes.push_back(node);
	  index = SubNodes.size() - 1;
  }
  item->PathParts.pop_front();
  SubNodes[index]->AddItem(include, item);
}

void CCensorNode::AddItem(bool include, const CString &path, bool recursive, bool forFile, bool forDir)
{
	std::shared_ptr<CItem> item = std::make_shared<CItem>();
  SplitPathToParts(path, item->PathParts);
  item->Recursive = recursive;
  item->ForFile = forFile;
  item->ForDir = forDir;
  AddItem(include, item);
}

bool CCensorNode::NeedCheckSubDirs() const
{
  for (size_t i = 0; i < IncludeItems.size(); i++)
  {
    const auto &item = IncludeItems[i];
    if (item->Recursive || item->PathParts.size() > 1)
      return true;
  }
  return false;
}

bool CCensorNode::AreThereIncludeItems() const
{
  if (IncludeItems.size() > 0)
    return true;
  for (size_t i = 0; i < SubNodes.size(); i++)
    if (SubNodes[i]->AreThereIncludeItems())
      return true;
  return false;
}

bool CCensorNode::CheckPathCurrent(bool include, const CStringVector &pathParts, bool isFile) const
{
	const ItemArrayType &items = include ? IncludeItems : ExcludeItems;
  for (size_t i = 0; i < items.size(); i++)
    if (items[i]->CheckPath(pathParts, isFile))
      return true;
  return false;
}

bool CCensorNode::CheckPath(CStringVector &pathParts, bool isFile, bool &include) const
{
  if (CheckPathCurrent(false, pathParts, isFile))
  {
    include = false;
    return true;
  }
  include = true;
  bool finded = CheckPathCurrent(true, pathParts, isFile);
  if (pathParts.size() == 1)
    return finded;
  int index = FindSubNode(pathParts.front());
  if (index >= 0)
  {
    CStringVector pathParts2 = pathParts;
	pathParts2.pop_front();
    if (SubNodes[index]->CheckPath(pathParts2, isFile, include))
      return true;
  }
  return finded;
}

bool CCensorNode::CheckPath(const CString &path, bool isFile, bool &include) const
{
  CStringVector pathParts;
  SplitPathToParts(path, pathParts);
  return CheckPath(pathParts, isFile, include);
}

bool CCensorNode::CheckPath(const CString &path, bool isFile) const
{
  bool include;
  if (CheckPath(path, isFile, include))
    return include;
  return false;
}

bool CCensorNode::CheckPathToRoot(bool include, CStringVector &pathParts, bool isFile) const
{
  if (CheckPathCurrent(include, pathParts, isFile))
    return true;
  if (Parent == 0)
    return false;
  pathParts.push_front(Name);
  return Parent->CheckPathToRoot(include, pathParts, isFile);
}

/*
bool CCensorNode::CheckPathToRoot(bool include, const CString &path, bool isFile) const
{
  CStringVector pathParts;
  SplitPathToParts(path, pathParts);
  return CheckPathToRoot(include, pathParts, isFile);
}
*/

void CCensorNode::AddItem2(bool include, const CString &path, bool recursive)
{
  if (path.IsEmpty())
    return;
  bool forFile = true;
  bool forFolder = true;
  CString path2 = path;
  if (IsCharDirLimiter(path[path.GetLength() - 1]))
  {
    path2.Delete(path.GetLength() - 1);
    forFile = false;
  }
  AddItem(include, path2, recursive, forFile, forFolder);
}

void CCensorNode::ExtendExclude(const std::shared_ptr<CCensorNode> &fromNodes)
{
	ExcludeItems.insert(ExcludeItems.end(), fromNodes->ExcludeItems.begin(), fromNodes->ExcludeItems.end() );
  for (size_t i = 0; i < fromNodes->SubNodes.size(); i++)
  {
	  const auto & node = fromNodes->SubNodes[i];
    int subNodeIndex = FindSubNode(node->Name);
    if (subNodeIndex < 0)
	{
		std::shared_ptr<CCensorNode> newNode = std::make_shared<CCensorNode>(node->Name, this);
		SubNodes.push_back(newNode);
		subNodeIndex = SubNodes.size() - 1;
	}
    SubNodes[subNodeIndex]->ExtendExclude(node);
  }
}

int CCensor::FindPrefix(const CString &prefix) const
{
  for (size_t i = 0; i < Pairs.size(); i++)
    if (CompareFileNames(Pairs[i].Prefix, prefix) == 0)
      return i;
  return -1;
}

void CCensor::AddItem(bool include, const CString &path, bool recursive)
{
  CStringVector pathParts;
  if (path.IsEmpty())
    throw "Empty file path";
  SplitPathToParts(path, pathParts);
  bool forFile = true;
  if (pathParts.back().IsEmpty())
  {
    forFile = false;
	pathParts.pop_back();
  }
  const CString &front = pathParts.front();
  bool isAbs = false;
  if (front.IsEmpty())
    isAbs = true;
  else if (front.GetLength() == 2 && front[1] == _T(':'))
    isAbs = true;
  else
  {
    for (size_t i = 0; i < pathParts.size(); i++)
    {
      const CString &part = pathParts[i];
      if (part == _T("..") || part == _T("."))
      {
        isAbs = true;
        break;
      }
    }
  }
  int numAbsParts = 0;
  if (isAbs)
    if (pathParts.size() > 1)
      numAbsParts = pathParts.size() - 1;
    else
      numAbsParts = 1;
  CString prefix;
  for (int i = 0; i < numAbsParts; i++)
  {
    const CString &front = pathParts.front();
    if (DoesNameContainWildCard(front))
      break;
    prefix += front;
    prefix += CHAR_PATH_SEPARATOR;
	pathParts.pop_front();
  }
  int index = FindPrefix(prefix);
  if (index < 0)
  {
	  Pairs.push_back(CPair(prefix));
	  index = Pairs.size() - 1;
  }

  std::shared_ptr<CItem> item = std::make_shared<CItem>();
  item->PathParts = pathParts;
  item->ForDir = true;
  item->ForFile = forFile;
  item->Recursive = recursive;
  Pairs[index].Head->AddItem(include, item);
}

bool CCensor::CheckPath(const CString &path, bool isFile) const
{
  bool finded = false;
  for (size_t i = 0; i < Pairs.size(); i++)
  {
    bool include;
    if (Pairs[i].Head->CheckPath(path, isFile, include))
    {
      if (!include)
        return false;
      finded = true;
    }
  }
  return finded;
}

void CCensor::ExtendExclude()
{
  size_t i;
  for (i = 0; i < Pairs.size(); i++)
    if (Pairs[i].Prefix.IsEmpty())
      break;
  if (i == Pairs.size())
    return;
  int index = i;
  for (i = 0; i < Pairs.size(); i++)
    if (index != i)
      Pairs[i].Head->ExtendExclude(Pairs[index].Head);
}

}

}

}